class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        _ret.resize(n);
        _index.resize(n);

        // 初始化 index 数组
        for(int i = 0; i < n; i++)
            _index[i] = i;

        MergeSort(nums, nums.size());

        return _ret;
    }

    void MergeSort(vector<int>& nums, int n)
    {
        _MergeSort(nums, 0, n - 1);
    }

    // 归并排序子程序--降序
    void _MergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right) return;

        int mid = (right - left) / 2 + left;
        // 根据 mid 划分成两个序列：[left, mid] [mid + 1, right]

        _MergeSort(nums, left, mid);
        _MergeSort(nums, mid + 1, right);
        
        // 合并[left, mid] [mid + 1, right]
        int begin1 = left, end1 = mid;
        int begin2 = mid + 1, end2 = right;
        int i = 0;
        while(begin1 <= end1 && begin2 <= end2)
        {
            if(nums[begin1] <= nums[begin2])
            {
                tmpNums[i] = nums[begin2];
                tmpIndex[i++] = _index[begin2++];
            }
            else
            {
                _ret[_index[begin1]] += right - begin2 + 1;   // 重点
                tmpNums[i] = nums[begin1];
                tmpIndex[i++] = _index[begin1++];
            }
        }

        // 可能存在第一个序列中的数据没有全部放到 tmp 中
        while(begin1 <= end1)
        {
            tmpNums[i] = nums[begin1];
            tmpIndex[i++] = _index[begin1++];
        }

        // 可能存在第二个序列中的数据没有全部放到 tmp 中
        while(begin2 <= end2)
        {
            tmpNums[i] = nums[begin2];
            tmpIndex[i++] = _index[begin2++];
        }

        // 还原合并数组
        for(int i = left; i <= right; ++i)
        {
            nums[i] = tmpNums[i - left];
            _index[i] = tmpIndex[i - left];
        }
    }

private:
    vector<int> _ret;
    vector<int> _index;     // 记录 nums 中当前元素的原始下标
    int tmpNums[500010];     // nums 临时数组
    int tmpIndex[500010];    // index 临时数组
};